// Written by Craig'n'Dave
using System;
using System.Collections.Generic;
// Linked list using objects
namespace ConsoleApp1
{
    class Program
    {
        public class LinkedList
        {
            public class Node
            {
                public string data;
                public Node pointer;
            }

            public Node start;

            public bool add(string item)
            {
                // Check memory overflow
                try
                {
                    Node new_node = new Node();
                    new_node.data = item;
                    Node current_node = start;
                    // List is empty
                    if (current_node == null)
                    {
                        new_node.pointer = null;
                        start = new_node;
                    }
                    else
                    {
                        // Item becomes the new start item
                        if (string.Compare(item, current_node .data) < 0)
                        {
                            start = new_node;
                            new_node.pointer = current_node;
                        }
                        else
                        {
                            // Find correct position in the list
                            Node previous_node = null;
                            while ((current_node != null) && (string.Compare(current_node .data, item) < 0))
                            {
                                previous_node = current_node;
                                current_node = current_node.pointer;
                            }
                            new_node.pointer = previous_node.pointer;
                            previous_node.pointer = new_node;
                        }
                    }
                return true;
                }
                catch
                {
                    return false;
                }
            }
            public void delete(string item)
            {
                Node new_node = new Node();
                Node current_node = start;
                // Check the list is not empty
                if (current_node != null)
                {
                    // Item is the start node
                    if (item == current_node.data)
                    {
                        start = current_node.pointer;
                    }
                    else
                    {
                        // Find item in the list
                        Node previous_node = null;
                        previous_node = current_node;
                        while ((current_node != null) && (item != current_node.data))
                        {
                            previous_node = current_node;
                            current_node = current_node.pointer;
                        }
                        if (current_node != null)
                        {
                            previous_node.pointer = current_node.pointer;
                        }
                    }
                }
            }

            public List<string> output()
            {
                List<string> items = new List<string>();
                Node current_node = start;
                if (current_node != null)
                {
                    // Visit each node
                    while (current_node != null)
                    {
                        items.Add(current_node.data);
                        current_node = current_node.pointer;
                    }
                }
                return items;
            }

        }

        

        // Main program starts here
        static void Main(string[] args)
        {
            string[] items = { "Florida", "Georgia", "Delaware", "Alabama", "California", "Wyoming" };
            LinkedList linked_list = new LinkedList();
            // Adding items to the linked list
            for (int index = 0; index < items.Length; index++)
            {
                linked_list.add(items[index]);
            }
            // Deleting items from a linked list
            linked_list.delete("Florida");
            // Output the linked list
            List<string> contents = new List<string>();
            contents = linked_list.output();
            Console.WriteLine(String.Join(", ", contents));
        }
    }
}
